/*
 * main.cpp
 *
 *  Created on: 2008-11-7
 *      Author: fanliangliang
 */

#include <string>
#include <iostream>

using namespace std;

int match(const char* regexp, const char* text);
int matchhere(const char* regexp, const char* text);
int matchstar(int c, const char* regexp, const char* text);
int matchqo(int c, const char* regexp, const char* text);
int matchplus(int c, const char* regexp, const char* text);

int main(int argc, char** argv) {

	if (argc < 1) {
		return EXIT_FAILURE;
	}

	string str;
	while (getline(cin, str)) {
		if (match("^ab.*d$", str.c_str())) {
			cout << "match:" << str << endl;
		}
		if (str == "q") {
			break;
		}
	}

	return EXIT_SUCCESS;
}


/* match: search for regexp anywhere in text */
int match(const char* regexp, const char* text)
{
	if (regexp[0] == '^')
		return matchhere(regexp+1, text);
	do {    /* must look even if string is empty */
		if (matchhere(regexp, text))
			return 1;
	} while (*text++ != '\0');
	return 0;
}

/* matchhere: search for regexp at beginning of text */
int matchhere(const char* regexp, const char* text)
{
	if (regexp[0] == '\0')
		return 1;
	if (regexp[1] == '?')
		return matchqo(regexp[0], regexp+2, text);
	if (regexp[1] == '+')
		return matchplus(regexp[0], regexp+2, text);
	if (regexp[1] == '*')
		return matchstar(regexp[0], regexp+2, text);

	if (regexp[0] == '$' && regexp[1] == '\0')
		return *text == '\0';
	if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text))
		return matchhere(regexp+1, text+1);
	return 0;
}

/* matchstar: search for c*regexp at beginning of text */
int matchstar(int c, const char* regexp, const char* text)
{
	do {   /* a * matches zero or more instances */
		if (matchhere(regexp, text))
			return 1;
	} while (*text != '\0' && (*text++ == c || c == '.'));
	return 0;
}

/* matchqo: search for c?regexp at beginning of text */
int matchqo(int c, const char* regexp, const char* text)
{
	int i = 0;
	do {   /* a * matches zero or more instances */
		if (matchhere(regexp, text))
			return 1;
		++i;
	} while (i < 2 && *text != '\0' && (*text++ == c || c == '.'));
	return 0;
}

/* matchplus: search for c+regexp at beginning of text */
int matchplus(int c, const char* regexp, const char* text)
{
	while (*text != '\0' && (*text++ == c || c == '.')) {
		if (matchhere(regexp, text))
			return 1;
	}
	return 0;
}
